package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

/**
 * 743. 网络延迟时间      https://leetcode.cn/problems/network-delay-time/
 */
public class LeetCode743 {

    static class Node {
        public int value;
        public ArrayList<Edge> edges = new ArrayList<>();

        public Node(int value) {
            this.value = value;
        }
    }

    static class Edge {
        public int weight;
        public Node from;
        public Node to;

        public Edge(int weight, Node from, Node to) {
            this.weight = weight;
            this.from = from;
            this.to = to;
        }
    }

    static class Record {
        public Node node;
        public int distinct;

        public Record(Node node, int distinct) {
            this.node = node;
            this.distinct = distinct;
        }
    }

    /**
     * 方法2，dijkstra + 加强堆
     */
    public static int networkDelayTime(int[][] times, int n, int k) {
        // 数据封装
        Map<Integer, Node> nodeMap = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            Node nodeFrom = nodeMap.getOrDefault(i, new Node(i));
            nodeMap.put(i, nodeFrom);
            for (int j = 0; j < times.length; j++) {
                int from = times[j][0];
                int to = times[j][1];
                int weight = times[j][2];
                if (from == i) {
                    Node nodeTo = nodeMap.getOrDefault(to, new Node(to));
                    nodeMap.put(to, nodeTo);
                    Edge edge = new Edge(weight, nodeFrom, nodeTo);
                    nodeFrom.edges.add(edge);
                }
            }
        }
        int ans = 0;
        // 数据处理
        Node node = nodeMap.get(k);
        NodeHeap nodeHeap = new NodeHeap(n);
        nodeHeap.addOrUpdateOrIgnore(node, 0);
        while (!nodeHeap.isEmpty()) {
            Record record = nodeHeap.pop();
            ans = Math.max(ans, record.distinct);
            for (Edge edge : record.node.edges) {
                nodeHeap.addOrUpdateOrIgnore(edge.to, record.distinct + edge.weight);
            }
        }
        // 判断有没有走过所有节点
        for (Node value : nodeMap.values()) {
            boolean exist = nodeHeap.nodeExist(value);
            if(!exist) {
                return -1;
            }
        }
        return ans;
    }

    static class NodeHeap {
        public Node[] nodes;
        public Map<Node, Integer> indexMap;
        public Map<Node, Integer> distinctMap;
        public int size;

        public NodeHeap(int n) {
            nodes = new Node[n];
            indexMap = new HashMap<>();
            distinctMap = new HashMap<>();
            size = 0;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public void addOrUpdateOrIgnore(Node node, int distinct) {
            // add
            if (!indexMap.containsKey(node)) {
                nodes[size] = node;
                indexMap.put(node, size);
                distinctMap.put(node, distinct);
                heapifyInsert(size++);
            } else if (indexMap.containsKey(node) && indexMap.get(node) != -1) {
                // update
                if (distinctMap.get(node) > distinct) {
                    distinctMap.put(node, distinct);
                    heapifyInsert(indexMap.get(node));
                }
            }
            // ignore(已选过节点不做操作-出过堆的数据)
        }

        // 弹出堆上元素
        public Record pop() {
            Node firstNode = nodes[0];
            Node lastNode = nodes[size - 1];
            Record record = new Record(firstNode, distinctMap.get(firstNode));
            swap(firstNode, lastNode);
            distinctMap.remove(firstNode);
            indexMap.put(firstNode, -1);
            nodes[size - 1] = null;
            size--;
            heapify(lastNode, size);
            return record;
        }

        public void heapifyInsert(int index) {
            while (distinctMap.get(nodes[index]) < distinctMap.get(nodes[(index - 1) / 2])) {
                swap(nodes[index], nodes[(index - 1) / 2]);
                index = (index - 1) / 2;
            }
        }

        public void heapify(Node node, int size) {
            int index = indexMap.get(node);
            if (index == -1) return;
            int left = 2 * index + 1;
            while (left < size) {
                int larges = ((left + 1 < size) && (distinctMap.get(nodes[left]) > distinctMap.get(nodes[left + 1])))
                        ? left + 1
                        : left;
                if (distinctMap.get(node) <= distinctMap.get(nodes[larges])) {
                    break;
                }
                swap(node, nodes[larges]);
                left = 2 * larges + 1;
            }
        }

        public void swap(Node node1, Node node2) {
            Integer index1 = indexMap.get(node1);
            Integer index2 = indexMap.get(node2);
            nodes[index1] = node2;
            nodes[index2] = node1;
            indexMap.put(node2, index1);
            indexMap.put(node1, index2);
        }

        public boolean nodeExist(Node node) {
            return indexMap.containsKey(node);
        }
    }

    // ----------------------------------------------------

//    /**
//     * 方法1
//     */
//    // time:{from,to,weight}    n个节点    从第k个节点出发
//    public static int networkDelayTime(int[][] times, int n, int k) {
//        Map<Node, Integer> distinctMap = new HashMap<>();
//        Set<Node> selectNode = new HashSet<>();
//        // 所有节点、边
//        Map<Integer, Node> nodeMap = new HashMap<>();
////        ArrayList<Edge> edges = new ArrayList<>();
//        for (int i = 0; i < times.length; i++) {
//            int fromValue = times[i][0];
//            int toValue = times[i][1];
//            Node fromNode = nodeMap.getOrDefault(fromValue, new Node(fromValue));
//            nodeMap.put(fromValue, fromNode);
//            Node toNode = nodeMap.getOrDefault(toValue, new Node(toValue));
//            nodeMap.put(toValue, toNode);
//            fromNode.edges.add(new Edge(times[i][2], fromNode, toNode));
//        }
//        Node curNode = nodeMap.get(k);
//        distinctMap.put(curNode, 0);
//        Node minNode = getMinNode(distinctMap, selectNode);
//        while (minNode != null) {
//            Integer distinct = distinctMap.get(minNode);
//            for (Edge edge : minNode.edges) {
//                Node toNode = edge.to;
//                if (!distinctMap.containsKey(toNode)) {
//                    distinctMap.put(toNode, distinct + edge.weight);
//                } else {
//                    distinctMap.put(toNode, Math.min(distinctMap.get(toNode), distinct + edge.weight));
//                }
//            }
//            selectNode.add(minNode);
//            minNode = getMinNode(distinctMap, selectNode);
//        }
//        int ans = -1;
//        if (distinctMap.values().size() < n) {
//            return ans;
//        }
//        for (Integer value : distinctMap.values()) {
//            ans = Math.max(ans, value);
//        }
//        return ans;
//    }
//
//    public static Node getMinNode(Map<Node, Integer> distinctMap, Set<Node> selectNode) {
//        Node minNode = null;
//        int min = Integer.MAX_VALUE;
//        for (Node node : distinctMap.keySet()) {
//            Integer distinct = distinctMap.get(node);
//            if (!selectNode.contains(node) && distinct < min) {
//                minNode = node;
//                min = distinct;
//            }
//        }
//        return minNode;
//    }

    public static void main(String[] args) {
        int[][] times = {{2, 1, 1}, {2, 3, 1}, {3, 4, 1}};
        System.out.println(networkDelayTime(times, 4, 2));       // 2
    }
}
